/*
 * @Author: wwssaabb
 * @Date: 2021-12-01 17:27:26
 * @LastEditTime: 2021-12-02 09:33:08
 * @FilePath: \handwritten-code\algorithm\最大正方形.js
 */

/* 
在一个由 0 和 1 组成的二维矩阵内， 找到只包含 1 的最大正方形， 并返回其面积
*/

let matrix = [
  [1, 0, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 1, 1, 1, 1],
  [1, 0, 0, 1, 1],
]

//如果现在是 1,1, 看0,0、1,0 、0,1最小值如果为0则不满足，为0+1；都为1则1+1；都为2则2+1 ...

var maximalSquare = function (matrix) {
  if (!matrix.length) return 0
  let maxsqlen = 0,
    rowLen = matrix.length,
    colLen = matrix[0].length
  for (let row = 0; row < rowLen; row++) {
    for (let col = 0; col < colLen; col++) {
      if (matrix[row][col] === '1') {
        matrix[row][col] = Number(matrix[row][col])
        if (row !== 0 && col !== 0) {
          matrix[row][col] = Math.min(matrix[row - 1][col], matrix[row][col - 1], matrix[row - 1][col - 1]) + 1
        }
        maxsqlen = Math.max(maxsqlen, matrix[row][col])
      }
    }
  }
  return maxsqlen ** 2
}
console.log(maximalSquare(matrix))